package com.sjc.algorithm.sort;

import java.util.Arrays;

/**
 * 堆排序
 * @author by SangJiacun
 * @Date 2020/5/12 10:44
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,3,2,6,5,7,8,9,10,0};
        sort(arr);
        System.out.println(Arrays.toString(arr)); //[0, 1, 2, 3, 5, 6, 7, 8, 9, 10]
    }

    /**
     * 出队，下沉操作
     * 删除堆顶的元素，把堆最后一个节点 临时 补到原本堆的位置
     * 让暂处于堆顶的节点和它的左右子孩子比较。 和最小的子孩子进行交换
     * @param arr 待调整的堆
     * @param parent 要下沉的父节点
     * @param length 堆的有效大小
     */
    private static void downAdjust(int[] arr,int parent, int length){
        int temp = arr[parent];

        int child = parent*2 +1;
        while(child < length){
            // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
            if(child+1 < length && arr[child+1] > arr[child]){
                child++;
            }

            // 如果父节点大于等于任何一个孩子的值，直接跳出
            if(temp >= arr[child]){
                break;
            }
            // 无须真正交换，单向赋值
            arr[parent] = arr[child];
            parent = child;

            // 上一层的子节点 变成了 下一层的父节点，
            child = child*2 +1;
        }
        arr[parent] = temp;
    }

    /**
     * 入队，上浮操作
     * 插入位置 是 二叉树的最后一个位置
     * 新节点与父节点比较，如果父节点大，和父节点交换位置，"上浮"
     * @param arr
     */
    private static void sort(int[] arr){
        // 使用下沉操作 构建最大堆
        // 从 最后一个节点的父节点 开始往前遍历所有叶子节点
        for(int i= (arr.length-2)/2; i>=0; i--){
            downAdjust(arr, i, arr.length);
        }

        System.out.println(Arrays.toString(arr));// [10, 9, 8, 6, 5, 7, 2, 3, 1, 0]

        // 堆顶元素 和 堆最后一个元素 互换：
        // 1. 最大值放到末尾，
        // 2. 上浮操作 需要将最后一个元素放到堆顶。
        // 3. 下次循环 堆的节点个数 -1
        for(int i= arr.length-1; i>0; i--){
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            downAdjust(arr,0,i);
        }
    }
}
